import java.util.*;

//二叉树
class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(char val){
        this.val = val;
    }
}

public class BinaryTree {

    //创建一个二叉树
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

    //前序遍历
    public void preOrder(TreeNode node){
        if (node == null){
            return;
        }
        System.out.print(node.val + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
    public List<Character> preOrder1(TreeNode node){
        List<Character> list = new ArrayList<>();
        if (node == null){
            return list;
        }
        list.add(node.val);
        List<Character> left = preOrder1(node.left);
        list.addAll(left);
        List<Character> right = preOrder1(node.right);
        list.addAll(right);
        return list;
    }
    //非递归前序
    public void preOrder2(TreeNode node){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = node;
        while (cur != null || !stack.empty()) {//注意栈不为空还要继续弹出
            while (cur != null) {
                stack.push(cur);//放入栈
                System.out.println(cur.val);//再打印
                cur = cur.left;//往左遍历
            }
            //此时cur左边判断完了，弹出栈顶元素
            TreeNode top = stack.pop();
            //判断栈顶元素右边是否为null
            cur = top.right;
        }
    }


    //中序遍历
    public void inOrder(TreeNode node){
        if (node == null){
            return;
        }
        inOrder(node.left);
        System.out.print(node.val + " ");
        inOrder(node.right);
    }
    public List<Character> inOrder1(TreeNode node){
        List<Character> list = new ArrayList<>();
        if (node == null){
            return list;
        }
        List<Character> left = inOrder1(node.left);
        list.addAll(left);
        list.add(node.val);
        List<Character> right = inOrder1(node.right);
        list.addAll(right);
        return list;
    }
    //非递归中序
    public void inOrder2(TreeNode node){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = node;
        while (cur != null || !stack.empty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.println(top.val);
            cur = top.right;
        }
    }


    //后序遍历
    public void postOrder(TreeNode node){
        if (node == null){
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.val + " ");
    }
    public List<Character> postOrder1(TreeNode node){
        List<Character> list = new ArrayList<>();
        if (node == null){
            return list;
        }
        List<Character> left = postOrder1(node.left);
        list.addAll(left);
        List<Character> right = postOrder1(node.right);
        list.addAll(right);
        list.add(node.val);
        return list;
    }
    //非递归前序
    public void postOrder2(TreeNode node){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = node;
        TreeNode prev = null;
        while (cur != null || !stack.empty()) {//注意栈不为空还要继续弹出
            while (cur != null) {
                stack.push(cur);//放入栈
                cur = cur.left;//往左遍历
            }
            //此时cur左边判断完了，取出栈顶元素
            TreeNode top = stack.peek();
            if (top.right == null || prev == top.right){//这里有个注意点，防止它打印的再打印，要记住打印的值
                //空就弹出并打印
                stack.pop();
                System.out.println(top.val);
                prev = top;
            }else {
                //非空到右边来
                cur = top.right;
            }
        }
    }

    //求树的所有节点
    //遍历思路：到一个节点count++，但是count要放在外面
    int count = 0;
    public int size(TreeNode node){
        if (node == null){
            return 0;
        }
        count++;
        size(node.left);
        size(node.right);
        return count;
    }
    //子问题思路：左树节点加上右树节点和自己即可
    public int size1(TreeNode node){
        if (node == null){
            return 0;
        }
        return size1(node.left) + size1(node.right) + 1;
    }

    //求叶子节点个数
    //遍历思路：加个条件再+1就行
    int count1 = 0;
    public int getLeafNodeCount(TreeNode node){
        if (node == null){
            return 0;
        }
        if (node.left == null && node.right == null){
            count1++;
        }
        getLeafNodeCount(node.left);
        getLeafNodeCount(node.right);
        return count1;
    }
    //子问题思路：左右树遇到都是null就加1
    public int getLeafNodeCount1(TreeNode node){
        if (node == null){
            return 0;
        }
        if (node.left == null && node.right == null){
            return 1;
        }
        return getLeafNodeCount1(node.left) + getLeafNodeCount1(node.right);
    }

    //求第k层有多少节点
    public int getLevelNodeCount(TreeNode node, int k){
        if (node == null){
            return 0;
        }//以防k过大，要加上
        if (k == 1){
            return 1;
        }
        return getLevelNodeCount(node.left, k - 1) +
                getLevelNodeCount(node.right, k - 1);
    }

    //获取二叉树高度:左树高度和右树高度的最大值加一
    public int getHeight1(TreeNode node){
        if (node == null){
            return 0;
        }
        if (node.left == null && node.right == null){
            return 1;
        }
        return Math.max(getHeight1(node.left), getHeight1(node.right)) + 1;
    }
    public int getHeight(TreeNode node){
        if (node == null){
            return 0;
        }
        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    //检测值为val的节点:先看根，再看左，再看右
    public TreeNode find(TreeNode node, char val){
        if (node == null){
            return null;
        }
        if (node.val == val){
            return node;
        }
        TreeNode left = find(node.left, val);
        TreeNode right = find(node.right, val);

        return left == null ? right : left;
    }

    //判断是否是完全二叉树
    //使用队列
    public boolean isCompleteTree(TreeNode node){
        if (node == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if (cur != null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()){
            if (queue.poll() != null){
                return false;
            }
        }
        return true;
    }

}
